/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxPathSum = function (root) {
  //存储最大值
  let maxValue = -1001

  function dfs(node) {
    //递归边界
    if (!node) {
      return 0
    }

    // 递归计算左右最大路径和，如果小于0则不取（相当于剪枝）
    let left = Math.max(dfs(node.left), 0)
    let right = Math.max(dfs(node.right), 0)
    //当前节点的最大路径和（左右都能选）
    let tempMax = left + right + node.val
    if (tempMax > maxValue) maxValue = tempMax

    // 返回当前节点可延伸最大路径和（只能往左或右走）
    return Math.max(left, right) + node.val
  }
  //调用递归函数求最大路径和
  dfs(root)

  return maxValue
};